#pragma once
#include <math.h>


template <typename T>
class SplitVector {
protected:
	T* body;
	int capicity;//capicity
	int length;
	int part1Length;
	int gapLength;	/// invariant: gapLength == size - lengthBody
	int growSize;

protected:
	/// Move the gap to a particular position so that insertion and
	/// deletion at that point will not require much copying and
	/// hence be fast.
	void GapTo( int position ) {
		if ( position != part1Length ) {
			if ( position < part1Length ) {
				memmove(
					body + position + gapLength,
					body + position,
					sizeof( T ) * ( part1Length - position ) );
			} else {	// position > part1Length
				memmove(
					body + part1Length,
					body + part1Length + gapLength,
					sizeof( T ) * ( position - part1Length ) );
			}
			part1Length = position;
		}
	}

	/// Check that there is room in the buffer for an insertion,
	/// reallocating if more space needed.
	void RoomFor( int insertionLength ) {
		if ( gapLength <= insertionLength ) {
			while ( growSize < capicity  ) {
				growSize *= 2;
			}
			ReAllocate( capicity + insertionLength + growSize );
		}
	}

	void Init() {
		if( body ) {
			delete[] body;
		}
		body = 0;
		growSize = 8;
		capicity = 0;
		length = 0;
		part1Length = 0;
		gapLength = 0;
	}

	int InnerIndex( int position )const {
		if( position < 0 ) {
			return 0;
		}
		if( position >= length ) {
			return 0;
		}
		assert( position >= 0 );
		assert( position < length );
		if ( position < part1Length ) {
			return position;
		} else {
			return gapLength + position;
		}
	}

public:
	/// Construct a split buffer.
	SplitVector(): body( 0 ) {
		Init();
	}

	SplitVector( int groupSize_ ): body( 0 ) {
		Init();
		SetGrowSize( groupSize_ );
		ReAllocate( groupSize_ );
	}

	virtual ~SplitVector() {
		delete []body;
		body = 0;
	}
	bool IsValidPos( int position ) {
		return position >= 0 && position < length;
	}
	bool IsValidInsertPos( int position ) {
		return position >= 0 && position <= length;
	}

	int GetGrowSize() const {
		return growSize;
	}

	void SetGrowSize( int growSize_ ) {
		growSize = growSize_;
	}

	/// Reallocate the storage for the buffer to be newSize and
	/// copy exisiting contents to the new buffer.
	/// Must not be used to decrease the size of the buffer.
	void ReAllocate( int newSize ) {
		if ( newSize > capicity ) {
			// Move the gap to the end
			GapTo( length );
			T* newBody = new T[newSize];
			if ( ( capicity != 0 ) && ( body != 0 ) ) {
				memmove( newBody, body, sizeof( T ) * length );
				delete []body;
			}
			body = newBody;
			gapLength += newSize - capicity;
			capicity = newSize;
		}
	}

	/// Retrieve the character at a particular position.
	/// Retrieving positions outside the range of the buffer returns 0.
	/// The assertions here are disabled since calling code can be
	/// simpler if out of range access works and returns 0.
	T ValueAt( int position ) const {
		int index = InnerIndex( position );
		return body[index];
	}

	void SetValueAt( int position, T v ) {
		int index = InnerIndex( position );
		body[index] = v;
	}

	T& operator[]( int position ) const {
		int index = InnerIndex( position );
		return body[index];
	}

	/// Retrieve the length of the buffer.
	int Length() const {
		return length;
	}

	/// Insert a single value into the buffer.
	/// Inserting at positions outside the current range fails.
	void Insert( int position, T v ) {
		Replace(position, 0, &v, 0, 1);
		/*assert( ( position >= 0 ) && ( position <= length ) );
		if( !( ( position >= 0 ) && ( position <= length ) ) ) {
			return;
		}

		RoomFor( 1 );
		GapTo( position );
		body[part1Length] = v;
		length++;
		part1Length++;
		gapLength--;*/
	}

	/// Insert a number of elements into the buffer setting their value.
	/// Inserting at positions outside the current range fails.
	void InsertValue( int position, int insertLength, T v ) {
		assert(IsValidInsertPos(position));
		assert(insertLength >=0);
		if(insertLength >0){
			T* arr = new T[insertLength];
			for(int i=0; i< insertLength; ++i){
				arr[i] = v;
			}
			Replace(position, 0, arr, 0, insertLength);
			delete [] arr;
		}
		/*assert( ( position >= 0 ) && ( position <= length ) );
		if( !( ( position >= 0 ) && ( position <= length ) ) ) {
			return;
		}
		if ( insertLength > 0 ) {
			RoomFor( insertLength );
			GapTo( position );
			for ( int i = 0; i < insertLength; i++ ) {
				body[part1Length + i] = v;
			}
			length += insertLength;
			part1Length += insertLength;
			gapLength -= insertLength;
		}*/
	}

	/// Ensure at least length elements allocated,
	/// appending zero valued elements if needed.
	void EnsureLength( int wantedLength ) {
		if ( Length() < wantedLength ) {
			InsertValue( Length(), wantedLength - Length(), 0 );
		}
	}

	/// Insert text into the buffer from an array.
	void InsertFromArray( int positionToInsert, const T s[], int positionFrom, int insertLength ) {
		Replace(positionToInsert, 0, s, positionFrom, insertLength);
		/*assert( ( positionToInsert >= 0 ) && ( positionToInsert <= length ) );
		if ( insertLength > 0 ) {
			if ( ( positionToInsert < 0 ) || ( positionToInsert > length ) ) {
				return;
			}
			RoomFor( insertLength );
			GapTo( positionToInsert );
			memmove( body + part1Length, s + positionFrom, sizeof( T ) * insertLength );
			length += insertLength;
			part1Length += insertLength;
			gapLength -= insertLength;
		}*/
	}

	/// Delete one element from the buffer.
	void Delete( int position ) {
		DeleteRange( position, 1 );
	}

	/// Delete a range from the buffer.
	/// Deleting positions outside the current range fails.
	void DeleteRange( int position, int deleteLength ) {
		Replace(position, deleteLength, 0, 0, 0);
		//assert( ( position >= 0 ) && ( position + deleteLength <= length ) );
		//if ( ( position < 0 ) || ( ( position + deleteLength ) > length ) ) {
		//	return;
		//}
		//if ( ( position == 0 ) && ( deleteLength == length ) ) {
		//	// Full deallocation returns storage and is faster
		//	delete []body;
		//	Init();
		//} else if ( deleteLength > 0 ) {
		//	GapTo( position );
		//	length -= deleteLength;
		//	gapLength += deleteLength;
		//}
	}

	/// Delete all the buffer contents.
	void DeleteAll() {
		DeleteRange( 0, length );
	}
	void Replace( int from, int sizeToReplace, const T* src, int srcFrom, int sizeSrc ) {
		assert( from >= 0 );
		assert( sizeToReplace >= 0 );
		assert( sizeSrc >= 0 );
		//srcFrom maybe <0
		if( src == NULL || sizeSrc <= 0 ) {
			//delete
			if ( sizeToReplace > 0 ) {
				assert( from + sizeToReplace <= length  );
				GapTo( from );
				length -= sizeToReplace;
				gapLength += sizeToReplace;
			}//else delete nothing
		} else { //src != null and sizeSrc>0
			if( sizeToReplace == 0 ) {
				//insert
				if ( sizeSrc > 0 ) {
					assert(  from <= length  );
					RoomFor( sizeSrc );
					GapTo( from );
					memmove( body + from, src + srcFrom, sizeof( T ) * sizeSrc );
					length += sizeSrc;
					part1Length += sizeSrc;
					gapLength -= sizeSrc;
				}//else insert nothing
			} else if( sizeToReplace > 0 ) {
				//replace
				assert( from + sizeToReplace <= length  );
				if( sizeSrc == sizeToReplace ) {
					GapTo( from + sizeToReplace );
					memmove( body + from, src + srcFrom, sizeof( T ) * sizeSrc );
				} else if( sizeSrc > sizeToReplace ) {
					int delta = sizeSrc - sizeToReplace;
					RoomFor( delta );
					GapTo( from + sizeToReplace );
					memmove( body + from, src + srcFrom, sizeof( T ) * sizeSrc );
					length += delta;
					part1Length += delta;
					gapLength -= delta;
				} else {
					int delta = sizeToReplace - sizeSrc;
					GapTo( from + sizeToReplace );
					memmove( body + from, src + srcFrom, sizeof( T ) * sizeSrc );
					length -= delta;
					part1Length -= delta;
					gapLength += delta;

				}
			}//else sizeToReplace <0, invalid

		}


	}

	// Retrieve a range of elements into an array
	void GetRange( T* buffer, int position, int retrieveLength ) const {
		// Split into up to 2 ranges, before and after the split then use memcpy on each.
		int range1Length = 0;
		if ( position < part1Length ) {
			int part1AfterPosition = part1Length - position;
			range1Length = retrieveLength;
			if ( range1Length > part1AfterPosition ) {
				range1Length = part1AfterPosition;
			}
		}
		memcpy( buffer, body + position, range1Length * sizeof( T ) );
		buffer += range1Length;
		position = position + range1Length + gapLength;
		int range2Length = retrieveLength - range1Length;
		memcpy( buffer, body + position, range2Length * sizeof( T ) );
	}

	T* BufferPointer() {
		RoomFor( 1 );
		GapTo( length );
		body[length] = 0;
		return body;
	}


	//[start, end)
	void RangeAddDelta( int start, int end, T delta ) {
		// end is 1 past end, so end-start is number of elements to change
		int i = 0;
		int rangeLength = end - start;
		int range1Length = rangeLength;
		int part1Left = part1Length - start;
		if ( range1Length > part1Left ) {
			range1Length = part1Left;
		}
		while ( i < range1Length ) {
			body[start++] += delta;
			i++;
		}
		start += gapLength;
		while ( i < rangeLength ) {
			body[start++] += delta;
			i++;
		}
	}
};


